A digital data processing system comprises at least a memory element, an input-output element and a processor element; and it may contain plural numbers of any or all of them. The memory element stores information in addressable storage locations. This information includes data and instructions for processing the data, including commands and responses. The processor element transfers information to and from the memory element, intreprets the incoming information as either data or instructions and processes data in accordance with the instructions. Input-output elements also communicate with the memory element(s) in order to transfer input data to and from the system and to obtain and process data from it.
Over the years, many different types of digital data processing systems have been developed. In recent years, developments have included computer networks wherein multiple memory elements, input-output elements and processor elements, often located at different positions, are enabled to communicate with each other. Among the types of information transfer schemes which are available, a general requirement is the use of a shared communications resource (i.e., channel or bus) which interconnects the various elements. With such sharing of the communications resource, network efficiency and utilization is strongly affected by the procedure for controlling access to the communications resource. Waiting time and other time consumed in overhead operations during which no transfer occurs detract from operational efficiency.
In general, a transmission between two units over a communications bus requires two steps, since more than one unit has the capability of originating such a connection. The first step is for the initiating unit to obtain control of the bus for some more or less defined interval. Once the selection step is completed, a second (or transfer) step is used to complete the transfer that is controlled by the selected initiating unit.
Obtaining control of the bus requires contending with other units desiring bus access, to arbitrate and determine which one will be selected. There are two principal generic approaches to arbitration. These are central arbitration and distributed arbitration. In central arbitration, a single, central priority circuit or device receives all requests for bus access and determines which requesting unit at any given time should be accorded the greatest priority and allowed to use the bus. Once that unit is selected, it is allowed to control the bus and effect the transfer. By contrast, in distributed arbitration, each unit connected to the bus is assigned a specific priority and each unit individually determines whether it has sufficient priority to obtain control of the bus when it desires to do so. If a unit of higher priority simultaneously seeks bus access, a device of lower priority must wait until some later time when it is the highest priority requester.
According to one such scheme described in U.S. Pat. No. 4,229,791, issued Oct. 21, 1980 for DISTRIBUTED ARBITRATION CIRCUITRY FOR DATA PROCESSING SYSTEM and assigned to the same assignee as the present invention, for example, the bus is provided with an assigned arbitration conductor. As each unit is prepared to effect an information exchange, it transmits a request signal onto that conductor; the unit then compares its request level with all other requests and only if there is no higher priority level request does it grant itself control of the bus.
That system is not workable, however, when the bus comprises a single bit-serial line, since there is no separate arbitration conductor. In such systems, one approach which has been adopted is referred to as carrier-sense multiple access with collision detection (CSMA/CD). In a CSMA/CD network, each device or unit connected to the network controls its own access to the bus (which is generally a coaxial cable). Each device which uses the bus connects to the cable through an interface which includes apparatus for transmitting a signal onto the channel as well as apparatus for receiving a signal placed thereon by another device's interface. Each interface includes circuitry for monitoring the channel and indicating whenever two devices are transmitting at the same time. When a device which is transmitting detects that another device is transmitting at the same time, the two devices stop transmitting and signal to their associated information sources (which are supplying the information to be transmitted) to stop transmitting. Both then retry transmission after the channel is clear.
Each device that wants to use (i.e., transmit on) the channel first "listens" to hear if any other unit is transmitting. If it detects no other transmission, the station (i.e., unit) starts its transmission, while simultaneously "listening" to the channel. If it detects that another station has started transmitting at the same time, both detect the collision and stop, as noted above. To avoid repeated collisions, each then waits briefly and tries again; various approaches exist for assigning to each unit a unique or suitable random delay to control the interval prior to retransmission. Such a system is illustrated, for example, in U.S. Pat. No. 4,063,220, issued Dec. 13, 1977 to Robert M. Metcalfe et al. The same assignee as the present invention also has copending herewith the following previously filed applications which relate to a CSMA/CD network:
U.S. patent application Ser. No. 267,394, filed May 26, 1981 by Jesse B. Lipcon and titled TRANSCEIVER FOR LOCAL NETWORK USING CARRIER-SENSE MULTIPLE ACCESS/COLLISION DETECTION.
U.S. patent application Ser. No. 292,003, filed Aug. 11, 1981 by Jesse B. Lipcon and titled APPARATUS FOR TESTING COLLISION-DETECT CIRCUITRY IN A TRANSCEIVER FOR A LOCAL NETWORK USING CARRIER-SENSE MULTIPLE ACCESS/COLLISION DETECTION.
U.S. patent application Ser. No. 292,004, filed Aug. 11, 1981 by Jesse B. Lipcon and titled RELIABILITY ENHANCEMENTS FOR TRANCEIVERS FOR LOCAL DATA NETWORKS USING CARRIER-SENSE MULTIPLE ACCESS/COLLISION DETECTION.
U.S. patent application Ser. No. 292,005, filed Aug. 11, 1981 by Jesse B. Lipcon and titled CURRENT SOURCE TRANSMITTER OUTPUT STAGE FOR TANSCEIVER FOR LOCAL DATA NETWORKS.
U.S. patent application Ser. No. 292,006, filed Aug. 11, 1981 by Jesse B. Lipcon and titled PRECISION SETTING OF CURRENTS AND REFERENCE VOLTAGES.
A slightly different system is marketed by Network Systems Corporation, 6820 Shingle Creek Parkway, Brookline Center, Minn. 55430, and is described in C. Weitzman, Distributed Micro/Minicomputer Systems: Structure, Implementation and Application, .sctn. 4.3 at 180-183, Prentice Hall, Inc. 1980. In that system, when directed to transmit, an adapter (i.e., the interface to the coaxial cable) contends for use of the channel. Three mechanisms are used within the contention procedure. The first mechanism is carrier sensing: If the coaxial cable is busy (i.e., a signal is detected), the unit will not initiate transmission. The second mechanism involves delaying transmission, following detection of coaxial cable availability, by a fixed interval. Each interface contains a hardware delay element which prevents transmission from the time it senses the "cable not busy" condition until the delay has elapsed. This allows a receiver time to respond promptly to a transmission on termination of the message, without having to contend for the bus again; it also allows an adapter that has access to the cable to continue to use it in a series of transmissions. This fixed delay is 4 nanoseconds per foot of cable length and, for a 1,000 foot bus, it is therefore 8 microseconds (since it is necessary to allow for the trailing edge of the transmission to travel the full length and for the leading edge of a response to also travel the full length). The third mechanism assigns a transmission priority to each adapter. Following the bus becoming not busy and the fixed delay having elapsed, each adapter generates a time pulse at which time it may initiate transmission on the bus and capture the bus for its use. The time following the end of the fixed delay at which a bus interface generates the time pulse enabling a transmission to start is referred to as "n-delay". For adaptor 0, n-delay is 0. For all other adaptors, n-delay is given by the following formula: EQU n-delay=(n-1 delay)+(4 ns) (distance between node n-1 and node n, in feet)
If the bus is not busy and the two delay intervals have elapsed, an adapter immediately can initiate transmission. If collision occurs due to nearly simultaneous transmission by two adapters, it will be resolved during a retry, with the adapter having the higher priority being the one to get access.
Since priority designations for each adapter are predetermined in the Network Systems Corporation approach, one or more nodes may significantly dominate bus access time to the detriment of others. Indeed, it is only probabilistic, not deterministic, how long a node will have to wait for an opening. These are considerable drawbacks.
Accordingly, it is an object of the present invention to provide a distributed arbitration mechanism exhibiting greater fairness, wherein each node or unit connected to the bus has substantially equal average priority for obtaining bus access.
It is a further object of this invention to provide such an arbitration mechanism which is efficient and keeps retries to a minimum.
Yet another object of this invention is to provide a high reliability arbitration mechanism.
Still another object of this invention is to provide an arbitration mechanism which exhibits deterministic, not simply statistical behavior.
Yet another object is to provide an arbitration mechanism which permits a node to contend with two or more bus channels over which the node may communicate alternatively.
A further object of this invention is to provide an arbitration mechanism which satisfies one or more of the foregoing objectives and is relatively simple to implement.